package com.zhugang.week06;

/**
 * @program algorithms
 * @description: binarySearchTree
 * @author: chanzhugang
 * @create: 2022/07/13 12:01
 */
public class BinarySearchTree2 {


    private Node root = null;

    /**
     * 查询：递归实现
     *
     * @param root
     * @param data
     * @return
     */
    public Node find_r(Node root, int data) {
        if (root == null) {
            return null;
        }
        if (root.data == data) {
            return root;
        }
        if (data < root.data) {
            return find_r(root.left, data);
        } else {
            return find_r(root.right, data);
        }
    }

    /**
     * 插入
     *
     * @param root
     * @param data
     */
    public void insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }
        insert_r(root, data);
    }

    private void insert_r(Node root, int data) {
        if (data > root.data) {
            // 右子树
            if (root.right == null) {
                root.right = new Node(data);
            } else {
                insert_r(root.right, data);
            }
        } else {
            // 左子树
            if (root.left == null) {
                root.left = new Node(data);
            } else {
                insert_r(root.left, data);
            }
        }
    }

    public class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }
}